/*
 * nwpu/2005/2005_3.c
 *
 * Harry Wei <harryxiyou@gmail.com> (C) 2013
 */

/*
 * The binary tree should be created
 * like following, for it is preorder.
 * INPUT: ABC%%DE%G%%F%%%
 *				   A
 *                / \
 *               B   %
 *              /  \
 *             C    D
 *            / \  / \
 *           %   % E   F
 *                / \ / \
 *               %  G %  %
 *                 / \
 *                %   %
 * NOTE: % means nothing, that is to say, 
 * it is NULL.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct b_tree {
	char e;
	struct b_tree *lchild;
	struct b_tree *rchild;
} BTree;

int createbt(BTree **bt) {
	char ch = 0;
//	char a = 0;

//	printf("enter func createbt.\n");
	scanf("%c", &ch);
	if ('%' == ch) {
#if 0
		(*bt)->lchild = NULL;
		(*bt)->rchild = NULL;
#endif
		(*bt) = NULL;
	} else {
		(*bt) = (BTree *) malloc(sizeof(BTree));
		if (NULL == (*bt)) {
			fprintf(stderr, "%s\n", "Allocate Error!");
			return -1;
		}
		(*bt)->e = ch;
		createbt(&((*bt)->lchild));
		createbt(&((*bt)->rchild));
	}
//	printf("leave func createbt.\n");
	return 0;
}

int preorder(BTree *bt) {
//	printf("enter func preorder.");
	if (NULL != bt) {
		printf("%c", bt->e);
		preorder(bt->lchild);
		preorder(bt->rchild);
	} else {
		printf("%c", '%');
	}
//	printf("leave func preorder.");
	return 0;
}

int inorder(BTree *bt) {
//	printf("enter func preorder.");
	if (NULL != bt) {
		inorder(bt->lchild);
		printf("%c", bt->e);
		inorder(bt->rchild);
	} else {
		printf("%c", '%');
	}
//	printf("leave func preorder.");
	return 0;
}

int postorder(BTree *bt) {
//	printf("enter func preorder.");
	if (NULL != bt) {
		postorder(bt->lchild);
		postorder(bt->rchild);
		printf("%c", bt->e);
	} else {
		printf("%c", '%');
	}
//	printf("leave func preorder.");
	return 0;
}

int main(int argc, char *argv[]) {
	int ret = 0;
	BTree *bt = NULL;

	/*Preorder way to create binary tree*/
	ret = createbt(&bt);
	if (0 > ret) {
		fprintf(stdout, "%s\n", "Create bit tree error!");
		goto out;
	}
	preorder(bt);
	printf("\n");
	inorder(bt);
	printf("\n");
	postorder(bt);
	printf("\n");
	/*TODO: free memory jobs, now, os do those*/
out:
	return ret;
}
